/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/6/6.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 给定一个未排序的整数数组，找出最长连续序列的长度。
 *
 * 要求算法的时间复杂度为 O(n)。
 *
 * 示例:
 * 输入: [100, 4, 200, 1, 3, 2]
 * 输出: 4
 * 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <unordered_set>

using namespace std;

#define MAX(a, b)   a > b ? a : b
class Solution {
public:
    static int longestConsecutive(vector<int>& nums) {
        /* 使用 hash set 存放 nums，同时可以去重 */
        unordered_set<int> num_set(nums.size());
        for(const int i : nums) {
//            num_set.insert(i);
            num_set.emplace(i); /* 比 insert 更好吗？我也不是很清楚 */
        }

        /* 遍历 set，每回合检测当前数是否存在上一个连续的数，并更新最长序列长度 */
        int max_length = 0;
        int curr_length, curr_num;
        for(const int num : num_set) {
            curr_length = 0;
            if(num_set.count(num - 1))
                continue;       /* 如果上一个连续存在，跳过该数，以后清算 */

            curr_num = num;
            curr_length++;

            /* 检查连续序列在整个 set 中 */
            while (num_set.count(++curr_num))
                curr_length++;

            max_length = MAX(curr_length, max_length);
        }

        return max_length;
    }
};

int main() {

    vector<int> input = { 100, 4, 200, 1, 3, 2 };
    int ans = Solution::longestConsecutive(input);
    cout << "ans: " << ans << endl;

    return 0;
}

